#pragma once

#include "functor.hpp"
#include "utility.hpp"

namespace zuck
{
    template <typename Size_>
    [[nodiscard]] Size_ __lg(Size_ n)
    {
        Size_ k = 0;
        for (; n != 1; n >>= 1) {
            ++k;
        }
        return k;
    }

// push_heap pop_heap make_heap adjust_heap
    template<
        typename _RandomIter,
        typename _Diff_t = ::zuck::iter_diff_t<_RandomIter>,
        typename _Val_t  = ::zuck::iter_traits_t<_RandomIter>,
        typename _Cmp    = ::zuck::less<_Val_t>
    >
    void __push_heap(_RandomIter first, _Diff_t holeIdx, _Diff_t topIdx, _Val_t Valty, _Cmp _pred)
    {
        _Diff_t parent = ((holeIdx - 1) >> 1);

        for (; holeIdx > topIdx && _pred(*(first + parent), Valty);)
        {
            *(first + holeIdx) = *(first + parent);
            holeIdx            = parent;
            parent             = ((holeIdx - 1) >> 1);
        }

        *(first + holeIdx) = Valty;
    }

    template<
        typename _RandomIter,
        typename _Diff_t = ::zuck::iter_diff_t<_RandomIter>,
        typename _Val_t  = ::zuck::iter_traits_t<_RandomIter>,
        typename _Cmp    = ::zuck::less<_Val_t>
    >
    void __adjust_heap(_RandomIter first, _Diff_t _holeIdx, _Diff_t _len, _Val_t Valty, _Cmp _pred)
    {
        _Diff_t topIndex    = _holeIdx;
        _Diff_t secondChild = (_holeIdx << 1) + 2;
        for (; secondChild < _len;) {
            if (_pred(*(first + secondChild), 
                *(first + (secondChild - 1))))
            {
                --secondChild;
            }
            *(first + _holeIdx) = *(first + secondChild);
            _holeIdx            = secondChild;
            secondChild       = ((secondChild + 1) << 1);
        }
        if (secondChild == _len) { // end iterator
            *(first + _holeIdx) = *(first + (secondChild - 1));
            _holeIdx            = secondChild - 1;
        }
        zuck::__push_heap(first, _holeIdx, topIndex, Valty, _pred);
    }

    template<
        typename _RandomIter, 
        typename _Val_t  = ::zuck::iter_traits_t<_RandomIter>,
        typename _Diff_t = ::zuck::iter_diff_t<_RandomIter>,
        typename _Cmp    = ::zuck::less<_Val_t>
    >
    void __pop_heap(_RandomIter first , _RandomIter last, _RandomIter result, _Val_t Valty, _Cmp _pred)
    {
        *result = *first;
        zuck::__adjust_heap(first, _Diff_t(0), _Diff_t(last - first), Valty, _pred);
    }

    template<
        typename RandomIter, 
        typename Valty = ::zuck::iter_traits_t<RandomIter>,
        typename _Cmp = ::zuck::less<Valty>
    >
    void insertion_sort_uncheck(RandomIter first, RandomIter last, _Cmp cmp = zuck::less<Valty>{})
    {
        auto _tmp = first;
        for (RandomIter q = first + 1; q < last; ++q) {
            if (cmp(*q, *_tmp)) {
                _tmp = q;
            }
        }
        for (; _tmp != first; --_tmp) {
            zuck::swap(*_tmp, *(_tmp - 1));
        }
        for (RandomIter i = first + 2; i < last; ++i) {
            _tmp = i;
            for (; cmp(*(_tmp), *(_tmp - 1));) {
                zuck::swap(*_tmp, *(_tmp - 1));
                --_tmp;
            }
        }
    }
}

